闲话

C好难,D好水.本场链接:Codeforces Round #592

A. Pens and Pencils

题目大意:一根钢笔可以写$c$篇文章,一根铅笔可以画$d$张画,最多只能带$k$支笔.要写$a$篇文章,画$b$幅画.问是否可以完成,如果可以,输出带的钢笔和铅笔的数量.
数据范围:
$1 \leq a,b,c,d,k \leq 100$

思路

至少要有上取整的$a/c$根钢笔和上取整的$b/d$根铅笔,加起来不到$k$就满足.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		int l = ceil(double(a) / c);
		int r = ceil(double(b) / d);
		if(l + r > k)	puts("-1");
		else printf("%d %d\n",l,r);
    }
    return 0;
}

B. Rooms and Staircases

原题大意:有一个$2*n$的棋盘,棋盘上下不是全部相连的,上下的相连关系由一个字符串$S$给出,如果$S_i=1$说明第$i$位上下的格子是联通的.现在有一个机器人,你可以任意指定他的初始位置,并且不能经过之前已经经过的边,问你最多能走过多少个格子.

数据范围:
$1 \leq n \leq 1000$

错解思路

显然如果能转向就转向,这个时候每一个$1$都可以给我提供$2$个的步数,如果不能转向,那就是$1$的贡献.直接扫描统计字符串即可.错了的原因是,初始位置是不固定的,而且不能简单地就这样统计$0$的步数,如果另一边可以绕一圈过来,就可能导致字符串位置上虽然是$0$,但是实际这一列的贡献是$2$的情况.

正解思路

很显然,如果我转向了一次,之后是可以再转回来的,如果我从最左端出发,那么走到一个最远的$1$之后绕一圈,这样的距离步数是最大的.于是可以统计最左端和最右端的$1$的位置,分别乘$2$表示我绕了一圈,统计答案即可.如果没有$1$那就只能走一条直线,答案为$n$.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
char s[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		scanf("%s",s + 1);getchar();
		int res = 0,L = 0x3f3f3f3f,R = -1;
		for(int i = 1;i <= n;++i)	
		{
			if(s[i] == '1')	
				L = min(L,i),R = max(R,i);
		}
		if(R == -1)	
		{
			printf("%d\n",n);
			continue;
		}
		res = max({res,L * 2,(n - L + 1) * 2});
		res = max({res,R * 2,(n - R + 1) * 2});
		printf("%d\n",res);
    }
    return 0;
}

C. The Football Season

题目大意:解不定方程:
$\begin{cases}x*w+y*d=p\\x+y+z=n\\ 0 \leq x,y,z \end{cases}$
其中$x,y,z$是未知数,其余已知.
求出一组解即可.

数据范围:
$1 \leq n \leq 10^{12}$
$0 \leq p \leq 10^{17}$
$1 \leq d < w \leq 10^5$

错解思路

这题要的就是找一个$x+y$最小的解,因为$x+y$越小留给$z$的空间就越大,如果最小值都比$n$大则无解,那求不定方程,直接上$exgcd$.错就错在数据范围太大了,如果直接$exgcd$显然会导致爆long long.

正解思路

想要知道怎么找$x+y$的最小的解的,一是消元,二是可以从方程入手:
不定方程$x*w + d*y = p$本身是没什么信息的,可以想办法等价变形,找出各个解的形式:
原式$=x*w + d*w + d*y - d*w = p$
$=(x + d)*w + (y - w)*d=p$
故不定方程的解都满足$x + k*d$以及$y - k*w$的形式.因为$w > d$,所以$y$减小的速度比$x$增大的速度快,进而如果$y$达到最小,那么$x+y$也就达到了最小.而所有的$y$满足$y-kw$这个形式,所以最终答案的最小的$y$的取值范围就是$[0,w)$.这一点是比较好想的,又注意到$w \leq10^5$所以可以直接枚举$y$的取值,如果合法就直接输出,全部都不合法就说明无解,因为最小的都不够用,就不可能有更好的情况了.另外有一个博客也是讲这个问题,推荐一下:关于ax+by=c的解x，y的min(|x|+|y|)值问题

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ll n,p,w,d;cin >> n >> p >> w >> d;
	ll sres = 0,resx = -1,resy = -1;
	for(ll y = 0;y < w;++y)
	{
		ll A = p - d * y;
		if(A % w == 0)
		{
			ll x = A / w;
			if(x >= 0 && x + y <= n)
			{
				cout << x << " " << y << " " << n - x - y << endl;
				return 0;
			}
		}
	}
	cout << "-1";
    return 0;
}

D. Paint the Tree

题目大意:有一个$n$点的无根树,给定每个节点染成某种颜色的代价.颜色只有三种,要求树上三个相连的节点颜色是不能相同的.求是否能染色这棵树,如果能,求出最小代价.

数据范围:
$1 \leq n \leq 10^5$
$1 \leq cost \leq 10^9$

思路

首先考虑什么时候无解:对于某一个点来说,如果与他相连的点达到$3$个或以上,就无解.这一点应该是很显然的,因为一旦连了$3$个点必然会导致颜色相同,因此整颗树上不存在一个度数为$3$的点.这就意味着:这棵树退化成了一个链.这是一个非常强的条件.找到了这个条件之后整个题就变得简单了:因为对于一个链来说,如果他的首/尾和与之相连的颜色确定了,那么整个链的颜色也就确定了.
首先找到一个度数为$1$的点,标记成根节点.枚举根节点和与之相邻的点的颜色,然后直接$dfs$确定整个链的代价.并记录代价和具体方案,统计一下即可.
注意权值很大,会爆int.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int cost[3][N],deg[N],n,col[N],rescol[N];
vector<int> edges[N];
ll res;
void dfs(int u,int fa,int c1,int c2)
{
	for(auto& v : edges[u])
	{
		if(v == fa)	continue;
		int c = 3 - c1 - c2;
		res += cost[c][v];
		col[v] = c;
		dfs(v,u,c2,c);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < 3;++i)
		for(int j = 1;j <= n;++j)
			scanf("%d",&cost[i][j]);
   	int root = 1,ok = 1;
   	for(int i = 1;i < n;++i)
   	{
   		int u,v;scanf("%d%d",&u,&v);
   		edges[u].push_back(v);++deg[u];
   		edges[v].push_back(u);++deg[v];
   	}
   	for(int i = 1;i <= n;++i)
   	{
   		if(deg[i] >= 3)
   		{
   			ok = 0;
   			break;
   		}
   		else if(deg[i] == 1)	root = i;
   	}
   	if(!ok)	puts("-1");
   	else
   	{
   		ll reres = 0x3f3f3f3f3f3f3f3f;
   		for(int i = 0;i < 3;++i)
   		{
   			for(int j = 0;j < 3;++j)
   			{
   				if(j == i)	continue;
   				res = cost[i][root] + cost[j][edges[root].back()];
   				col[root] = i;col[edges[root].back()] = j;
   				// cout << res << "*";
   				dfs(edges[root].back(),root,i,j);
   				// cout << i << " " << j << " " << res << endl;
   			   	if(reres > res)
	   			{
	   				reres = res;
	   				for(int i = 1;i <= n;++i)	rescol[i] = col[i];
	   			}
   			}
   		}
   		printf("%lld\n",reres);
   		for(int i = 1;i <= n;++i)	printf("%d ",rescol[i] + 1);
   	}
    return 0;
}

E. Minimizing Difference

题目大意:给定一个长度为$n$的序列,定义diff值为最大值和最小值的差值.你可以给序列里的任意一个元素加一或减一最多$k$次,问最小的diff值是多少.

数据范围:
$2 \leq n \leq 10^5$
$1 \leq k \leq 10^{14}$
$1 \leq a_i \leq 10^9$

思路

一开始应该能想到大概贪心直接构造是不行的,但是可以二分答案$x$判断$x$是否是答案.不过这个题就难在怎么写$check$框架上了.
如果答案是$x$的话,说明序列里所有的数都应该$\in [p,p+x]$这个区间,那么这个区间的取值有个特点,$p$或者$p+x$这两个数之间一定有一个数是$a$里的值,因为如果两者都不是的话,等价的减少到序列里的值,可以使答案减小,因此一定是有一个的.于是$check$就是在做两种分支:一种是以当前的$a_i$作为$p$另一种是以当前的$a_i$作为$p+x$进行判断.
假如整个序列里最后一个比$p$小的元素是$a_l$,第一个比$p+x$大的元素是$a_r$.那么修改次数就是左边和右边的部分加起来就行了.即修改次数$=p*l - \sum^l_{i=1} a_i - (p+x) * (n - r + 1) + \sum^n_{i=r} a_i$,求和部分可以前缀和.
最后考虑怎么找$p$和$p+x$.首先对于$a_i$是$p$的情况,要找的就是一个$a_j - a_i >= x$的最大的$j$之后的一位(额外加一位,使得$a_j - a_i > x$).其次对于$a_i$是$p + x$的情况,要找的就是一个$a_i - a_j >= x$的最小的一位.注意对于这两种情况而言,对应的$p$或$p+x$不一定是$a_j$.比如前者的$p+x$实际上是$a_i+x$,后者的$p$实际上是$a_i-x$.最后看答案是不是合法的就行了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
ll n,k,a[N],s[N];
bool check(int x)
{
	for(int i = 1,j = 1;i <= n;++i)
	{
		while(j <= n && a[j] - a[i] <= x)	++j;
		if(a[i] * (i - 1) - s[i - 1] + s[n] - s[j - 1] - (a[i] + x) * (n - j + 1) <= k)	return 1;
	}
	for(int i = 1,j = 1;i <= n;++i)
	{
		while(a[i] - a[j] > x)	++j;
		if((a[i] - x) * (j - 1) - s[j - 1] + s[n] - s[i] - a[i] * (n - i) <= k)	return 1;
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;++i)	cin >> a[i];
    sort(a + 1,a + 1 + n);
    for(int i = 1;i <= n;++i)	s[i] = s[i - 1] + a[i];
    int l = 0,r = a[n],res;
    while(l < r)
    {
    	int mid = l + r >> 1;
    	if(check(mid))	r = mid;
    	else l = mid + 1;
    }
    printf("%d",l);
    return 0;
}